/*********************************************************************************
 * 
 * MIT License
 *
 * Copyright (c) 2023 shaoguangcn
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 * 
 *********************************************************************************/

/**
 * \file charconv.hpp
 * An implementation of STL-charconv for pre-C++17
 */

#ifndef CHARCONV_HPP
#define CHARCONV_HPP

#include <limits>
#include <type_traits>
#include <system_error>
#include <cassert>

#ifdef CHARCONV_DEBUG
# define CHARCONV_ASSERT(x) assert((x))
#else
# define CHARCONV_ASSERT(x)
#endif

#ifndef CHARCONV_CPLUSPLUS
# ifdef _MSVC_LANG
#  define CHARCONV_CPLUSPLUS _MSVC_LANG
# else
#  define CHARCONV_CPLUSPLUS __cplusplus
# endif
#endif

#ifndef CXX11_CONSTEXPR
# if CHARCONV_CPLUSPLUS >= 201103L
#  define CXX11_CONSTEXPR constexpr
# else
#  define CXX11_CONSTEXPR
# endif
#endif

#ifndef CXX14_CONSTEXPR
# if CHARCONV_CPLUSPLUS >= 201402L
#  define CXX14_CONSTEXPR constexpr
# else
#  define CXX14_CONSTEXPR
# endif
#endif

#ifndef CXX17_CONSTEXPR
# if CHARCONV_CPLUSPLUS >= 201703L
#  define CXX17_CONSTEXPR constexpr
# else
#  define CXX17_CONSTEXPR
# endif
#endif

#ifndef CXX20_CONSTEXPR
# if CHARCONV_CPLUSPLUS > 201703L
#  define CXX20_CONSTEXPR constexpr
# else
#  define CXX20_CONSTEXPR
# endif
#endif

#ifndef CXX23_CONSTEXPR
# if CHARCONV_CPLUSPLUS > 202002L
#  define CXX23_CONSTEXPR constexpr
# else
#  define CXX23_CONSTEXPR
# endif
#endif

#ifndef CXX_IF_CONSTEXPR
# if CHARCONV_CPLUSPLUS >= 201703L && __cpp_if_constexpr
#  define CXX_IF_CONSTEXPR constexpr
# else
#  define CXX_IF_CONSTEXPR
# endif
#endif

// Check for an attribute
#ifndef CHARCONV_CHECK_FOR_CPP_ATTR
# if defined(__has_cpp_attribute)
#  define CHARCONV_CHECK_FOR_CPP_ATTR(x) __has_cpp_attribute(x)
# elif defined(__has_attribute)
#  define CHARCONV_CHECK_FOR_CPP_ATTR(x) __has_attribute(x)
# else
#  define CHARCONV_CHECK_FOR_CPP_ATTR(x) 0
# endif
#endif

#ifndef CHARCONV_CPP_ATTR_UNLIKELY
# if CHARCONV_CHECK_FOR_CPP_ATTR(unlikely)
#  define CHARCONV_CPP_ATTR_UNLIKELY [[unlikely]]
# else
#  define CHARCONV_CPP_ATTR_UNLIKELY
# endif
#endif

#ifndef CHARCONV_CPP_ATTR_LIKELY
# if CHARCONV_CHECK_FOR_CPP_ATTR(likely)
#  define CHARCONV_CPP_ATTR_LIKELY [[likely]]
# else
#  define CHARCONV_CPP_ATTR_LIKELY
# endif
#endif

#if defined(__GNUC__) || defined(__clang__)
#  define CHARCONV_LIKELY(x) __builtin_expect(!!(x), 1)
#  define CHARCONV_UNLIKELY(x) __builtin_expect(!!(x), 0)
#else
#  define CHARCONV_LIKELY(x) (x)
#  define CHARCONV_UNLIKELY(x) (x)
#endif

#if defined(__has_include) && __has_include(<bit>)
# include <bit> // for std::countl_zero()
#endif

#if CHARCONV_CPLUSPLUS > 201703L && __cpp_lib_bitops
# define CHARCONV_CPP_LIB_BITOPS __cpp_lib_bitops // for std::countl_zero()
#endif

/**
 * floating-point format for primitive numerical conversion
 */
enum class chars_format
{
    scientific = 1,
    fixed = 2,
    hex = 4,
    general = fixed | scientific
};

static constexpr chars_format operator|(chars_format lhs, chars_format rhs) noexcept
{
    return static_cast<chars_format>(static_cast<unsigned>(lhs) | static_cast<unsigned>(rhs));
}

static constexpr chars_format operator&(chars_format lhs, chars_format rhs) noexcept
{
    return static_cast<chars_format>(static_cast<unsigned>(lhs) & static_cast<unsigned>(rhs));
}

static constexpr chars_format operator^(chars_format lhs, chars_format rhs) noexcept
{
    return static_cast<chars_format>(static_cast<unsigned>(lhs) ^ static_cast<unsigned>(rhs));
}

static constexpr chars_format operator~(chars_format fmt) noexcept
{
    return static_cast<chars_format>(~static_cast<unsigned>(fmt));
}

static CXX14_CONSTEXPR chars_format& operator|=(chars_format& lhs, chars_format rhs) noexcept
{
    return lhs = lhs | rhs;
}

static CXX14_CONSTEXPR chars_format& operator&=(chars_format& lhs, chars_format rhs) noexcept
{
    return lhs = lhs & rhs;
}

static CXX14_CONSTEXPR chars_format& operator^=(chars_format& lhs, chars_format rhs) noexcept
{
    return lhs = lhs ^ rhs;
}

/**
 * Result type of to_chars().
 */
struct to_chars_result
{
    char* ptr;
    std::errc ec;
#if CHARCONV_CPLUSPLUS > 201703L && __cpp_impl_three_way_comparison >= 201907L
    friend bool operator==(const to_chars_result&, const to_chars_result&) = default;
#endif
};

/**
 * Result type of from_chars().
 */
struct from_chars_result
{
    const char* ptr;
    std::errc ec;
#if CHARCONV_CPLUSPLUS > 201703L && __cpp_impl_three_way_comparison >= 201907L
    friend bool operator==(const from_chars_result&, const from_chars_result&) = default;
#endif
};

/**
 * Determine the right size for a buffer to call to_chars().
 * 
 * \note This function is not in STL.
 */
template<typename T>
CXX14_CONSTEXPR unsigned int uint_to_chars_len(T value, int base = 10) noexcept;

/**
 * Determine the right size for a buffer to call to_chars().
 * 
 * \note This function is not in STL.
 */
template<typename T, typename std::enable_if<std::is_integral<T>::value>::type>
CXX17_CONSTEXPR unsigned int int_to_chars_len(T value, int base = 10) noexcept;

// to_chars(bool) should be deleted
to_chars_result to_chars(char*, char*, bool, int = 10) = delete;
to_chars_result to_chars(char* first, char* last, char value, int base = 10);
to_chars_result to_chars(char* first, char* last, signed char value, int base = 10);
to_chars_result to_chars(char* first, char* last, unsigned char value, int base = 10);
to_chars_result to_chars(char* first, char* last, short value, int base = 10);
to_chars_result to_chars(char* first, char* last, unsigned short value, int base = 10);
to_chars_result to_chars(char* first, char* last, int value, int base = 10);
to_chars_result to_chars(char* first, char* last, unsigned int value, int base = 10);
to_chars_result to_chars(char* first, char* last, long value, int base = 10);
to_chars_result to_chars(char* first, char* last, unsigned long value, int base = 10);
to_chars_result to_chars(char* first, char* last, long long value, int base = 10);
to_chars_result to_chars(char* first, char* last, unsigned long long value, int base = 10);

to_chars_result to_chars(char* first, char* last, float value);
to_chars_result to_chars(char* first, char* last, double value);
to_chars_result to_chars(char* first, char* last, long double value);

to_chars_result to_chars(char* first, char* last, float value, chars_format fmt);
to_chars_result to_chars(char* first, char* last, double value, chars_format fmt);
to_chars_result to_chars(char* first, char* last, long double value, chars_format fmt);

to_chars_result to_chars(char* first, char* last, float value, chars_format fmt, int precision);
to_chars_result to_chars(char* first, char* last, double value, chars_format fmt, int precision);
to_chars_result to_chars(char* first, char* last, long double value, chars_format fmt, int precision);


template<typename T>
CXX14_CONSTEXPR unsigned int uint_to_chars_len(T value, int base) noexcept
{
    static_assert(std::is_integral<T>::value, "implementation bug");
    static_assert(std::is_unsigned<T>::value, "implementation bug");

    unsigned int n = 1;
    const unsigned int b2 = base  * base;
    const unsigned int b3 = b2 * base;
    const unsigned long b4 = b3 * base;
    for ( ; ; ) {
        if (value < static_cast<unsigned int>(base)) {
            return n;
        }
        if (value < b2) {
            return n + 1;
        }
        if (value < b3) {
            return n + 2;
        }
        if (value < b4) {
            return n + 3;
        }
        value /= b4;
        n += 4;
	}
}

template<typename T, typename std::enable_if<std::is_integral<T>::value>::type>
CXX17_CONSTEXPR unsigned int int_to_chars_len(T value, int base) noexcept
{
    using unsigned_type = typename std::make_unsigned<T>::type;
    if CXX_IF_CONSTEXPR (std::is_unsigned<T>::value) {
        return uint_to_chars_len(value, base);
    } else {
        unsigned_type unisgned_value = static_cast<unsigned_type>(value);
        if (value < 0) {
            unisgned_value = static_cast<unsigned_type>(0 - value);
        }
        return uint_to_chars_len(unisgned_value, base);
    }
}

namespace detail {

template<typename...>
struct disjunction : std::false_type
{ };

template<typename B1>
struct disjunction<B1> : B1
{ };

template<typename B1, typename B2>
struct disjunction<B1, B2> : std::conditional<B1::value, B1, B2>::type
{ };

template<typename B1, typename B2, typename B3, typename... Bn>
struct disjunction<B1, B2, B3, Bn...> : std::conditional<B1::value, B1, disjunction<B2, B3, Bn...>>::type
{ };

// true if and only if T is in Types
template<typename T, class... Types>
using is_any_of = disjunction<std::is_same<T, Types>...>;

template<typename T>
using is_standard_unsigend_integer = 
    is_any_of<typename std::remove_cv<T>::type, 
        unsigned char, unsigned short, unsigned int, unsigned long, unsigned long long>;

} // namespace detail

/**
 * Returns the number of consecutive 0 bits in the value of \a x, starting from the most significant bit ("left").
 * 
 * Implementation of countl_zero without using specialized CPU instructions.
 * Used at compile time and when said instructions are not supported.
 * see "Hacker's Delight" section 5-3.
 * 
 * \param x value of unsigned integer type.
 * \return The number of consecutive 0 bits in the value of \a x, starting from the most significant bit.
 * \since C++20
 */
template<typename T, typename std::enable_if<detail::is_standard_unsigend_integer<T>::value, int>::type = 0>
CXX14_CONSTEXPR int countl_zero(T x) noexcept
{
#ifdef CHARCONV_CPP_LIB_BITOPS
    return std::countl_zero(x);
#else
    T val = 0;
    unsigned int n = std::numeric_limits<T>::digits;
    unsigned int c = std::numeric_limits<T>::digits / 2;
    do {
        val = static_cast<T>(x >> c);
        if (val != 0) {
            n -= c;
            x = val;
        }
        c >>= 1;
    } while (c != 0);
    return static_cast<int>(n) - static_cast<int>(x);
#endif
}

template<typename T, typename std::enable_if<detail::is_standard_unsigend_integer<T>::value, int>::type = 0>
CXX14_CONSTEXPR int countr_zero(T x) noexcept
{
#ifdef CHARCONV_CPP_LIB_BITOPS
    return std::countr_zero(x);
#else
    constexpr int digits = std::numeric_limits<T>::digits;
    return digits - countl_zero(static_cast<T>(~x) & static_cast<T>(x - 1));
#endif
}

template<typename T>
CXX14_CONSTEXPR int bit_width(T value) noexcept
{
    return std::numeric_limits<T>::digits - countl_zero(value);
}

#endif // CHARCONV_HPP